<?php
// This file is part of Preg question type - https://code.google.com/p/oasychev-moodle-plugins/
//
// Preg question type is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

/**
 * Defines subfunctions, which are used by finite automata equivalence check function.
 *
 * @package    qtype_preg
 * @copyright  2012 Oleg Sychev, Volgograd State Technical University
 * @author     Kamo Spertsian <spertsiankamo@gmail.com>
 * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
 */

defined('MOODLE_INTERNAL') || die();

global $CFG;
require_once($CFG->dirroot . '/question/type/preg/preg_fa.php');

/**
 * Class for pair of groups of two finite automata
 */
class qtype_preg_fa_pair_of_groups {
    /** @var reference to qtype_preg_fa_group object - first automata group. */
    public $first;
    /** @var reference to qtype_preg_fa_group object - second automata group. */
    public $second;
    /** @var first character on which it made transition to this group. */
    public $char;
    /** @var array of int tags on which it made transition to this group, */
    public $tags = array();

    public function __construct() {
        $first = new qtype_preg_fa_group;
        $second = new qtype_preg_fa_group;
    }

    public function compare($other) {
        return $this->first->cmpgroup($other->first) && $this->second->cmpgroup($other->second) &&
             $this->first->get_char() == $other->first->get_char() && $this->second->get_char() == $other->second->get_char()
             && $this->char == $other->char && $this->tags == $other->tags;
    }
}

/**
 * Compares two tag arrays (current and assigned) and generate largest common tag array
 */
function compare_current_transition_tags_array($arrayit, &$curtags) {
    // If current tag seqence is empty - return
    if (count($curtags) == 0) {
        return;
    }

    // If assigned sequence is empty - clear current and return
    if (current($arrayit) === false) {
        $curtags = array();
        return;
    }

    // When first tags are different - leave in current all tags, less then first
    if (current($arrayit) > $curtags[0]) {
        $k = 0;
        while ($k != count($curtags) && $curtags[$k] < current($arrayit)) {
            $k++;
        }
        while ($k != count($curtags)) {
            array_pop($curtags);
        }
        return;
    }

    if (current($arrayit) < $curtags[0]) {
        $curtagsmin = $curtags[0];
        $curtags = array();
        $it = $arrayit;
        while (current($it) !== false && current($it) < $curtagsmin) {
            array_push($curtags, current($it));
            next($it);
        }
        return;
    }

    // When some start tags are same
    for ($k = 0, $it = $arrayit; $k < count($curtags); $k++, next($it)) {
        if (current($it) === false || current($it) !== $curtags[$k]) {
            // Remove all tags from mismatch till the end
            while ($k < count($curtags)) {
                array_pop($curtags);
            }
        }
    }
}

/**
 * Comapres current tags array with assigned
 */
function compare_tag_sequences($arrayit, $curtags) {
    $temp = $arrayit;
    $i = 0;

    // While both comparing sequences has tags
    while (current($temp) !== false && $i < count($curtags)) {
        // If current comparing array tag is the same with cheking
        if (current($temp) === $curtags[$i]) {
            // Go to the next tag
            next($temp);
            $i++;
        }
        else {
            // If current comparing array tag is bigger then cheking
            if (current($temp) > $curtags[$i]) {
                // Comparing array doesn't contain all tags of checking array (because arrays are sorted)
                return false;
            }
            // Else go to the next comparing array tag
            next($temp);
        }
    }
    // Return true if count of same tags is equal to count of checking tags
    return $i == count($curtags);
}

/**
 * Compairs pairs of groups with same character
 */
function compare_groups($groups, $character, &$mismatches) {
    $clear = true;
    $cntsubpattern = 0;

    // Count nomber of existing mismatches of every type (automaton and subpattern)
    foreach ($mismatches as $mm) {
        $cntsubpattern += $mm->type == qtype_preg_fa_mismatch::SUBPATTERN;
    }

    // When there ae no pairs of groups with such character
    if (!array_key_exists($character, $groups)) {
        return true;
    }

    $firstempty = true;
    $secondempty = true;
    foreach($groups[$character] as $pair) {
        if (count($pair->tags)) {
            $firstempty = $pair->first->is_empty() || !$firstempty;
            $secondempty = $pair->second->is_empty() || !$secondempty;
        }
    }

    // Checking for character mismatch
    if (count($mismatches) - $cntsubpattern < 5 && count($groups[$character][0]->tags) == 0
        && ($groups[$character][0]->first->is_empty() && $firstempty || $groups[$character][0]->second->is_empty() && $secondempty)
        || count($groups[$character][0]->tags) && ($firstempty || $secondempty)) {
        $mm = new qtype_preg_fa_mismatch();
        $mm->character = $character;
        $mm->firstfaway = $groups[$character][0]->first->get_prev_groups();
        $mm->secondfaway = $groups[$character][0]->second->get_prev_groups();
        $mm->type = qtype_preg_fa_mismatch::CHARACTER;
        $tmp = $groups[$character][0]->first->get_states();
        $mm->firstfaindex = $groups[$character][0]->first->is_empty() ? 0 : (int)$pair->first->get_fa()->statenumbers[$tmp[0]];
        $tmp = $groups[$character][0]->second->get_states();
        $mm->secondfaindex = $groups[$character][0]->second->is_empty() ? 0 : (int)$pair->second->get_fa()->statenumbers[$tmp[0]];
        array_push($mismatches, $mm);
        $clear = false;
    }

    // Checking for final state mismatch
    foreach ($groups[$character] as $pair) {
        if (count($mismatches) - $cntsubpattern == 5) {
            break;
        }
        if (!$pair->first->is_empty() && !$pair->second->is_empty() && $pair->first->has_end_states() != $pair->second->has_end_states()) {
            $mm = new qtype_preg_fa_mismatch();
            $mm->character = $character;
            $mm->firstfaway = $pair->first->get_prev_groups();
            $mm->secondfaway = $pair->second->get_prev_groups();
            $mm->type = qtype_preg_fa_mismatch::FINAL_STATE;
            $mm->firstfaindex = 0;
            $mm->secondfaindex = 0;
            $ffa = $pair->first->get_fa();
            foreach ($pair->first->get_states() as $ind) {
                if ($ffa->has_endstate($ind)) {
                    $mm->firstfaindex = (int)$pair->first->get_fa()->statenumbers[$ind];
                }
            }
            $sfa = $pair->second->get_fa();
            foreach ($pair->second->get_states() as $ind) {
                if ($sfa->has_endstate($ind)) {
                    $mm->secondfaindex = (int)$pair->second->get_fa()->statenumbers[$ind];
                }
            }
            array_push($mismatches, $mm);
            $clear = false;
        }
    }

    // Checking for character but not subpattern mismatch
    if (count($mismatches) - $cntsubpattern < 5 && count($groups[$character][0]->tags) == 0
        && ($groups[$character][0]->first->is_empty() || $groups[$character][0]->second->is_empty()) && !$firstempty && !$secondempty) {
        $mm = new qtype_preg_fa_mismatch();
        $mm->character = $character;
        $mm->firstfaway = $groups[$character][0]->first->get_prev_groups();
        $mm->secondfaway = $groups[$character][0]->second->get_prev_groups();
        $mm->type = qtype_preg_fa_mismatch::CHARACTER_BUT_NOT_SUBPATTERN;
        $tmp = $groups[$character][0]->first->get_states();
        $mm->firstfaindex = $groups[$character][0]->first->is_empty() ? 0 : (int)$pair->first->get_fa()->statenumbers[$tmp[0]];
        $tmp = $groups[$character][0]->second->get_states();
        $mm->secondfaindex = $groups[$character][0]->second->is_empty() ? 0 : (int)$pair->second->get_fa()->statenumbers[$tmp[0]];
        array_push($mismatches, $mm);
        $clear = false;
    }

    // Checking for subpattern mismatch
    foreach ($groups[$character] as $pair) {
        if ($cntsubpattern == 5) {
            break;
        }
        if (count($pair->tags) && ($pair->first->is_empty() || $pair->second->is_empty())) {
            $mm = new qtype_preg_fa_mismatch();
            $mm->character = $character;
            $mm->firstfaway = $pair->first->get_prev_groups();
            $mm->secondfaway = $pair->second->get_prev_groups();
            $mm->type = qtype_preg_fa_mismatch::SUBPATTERN;
            $tmp = $pair->first->get_states();
            $mm->firstfaindex = $pair->first->is_empty() ? 0 : (int)$pair->first->get_fa()->statenumbers[$tmp[0]];
            $tmp = $pair->second->get_states();
            $mm->secondfaindex = $pair->second->is_empty() ? 0 : (int)$pair->second->get_fa()->statenumbers[$tmp[0]];
            $mm->tags = $pair->tags;
            array_push($mismatches, $mm);
            $clear = false;
        }
    }

    return $clear;
}

/**
 * Divides all outgoing transitions to intervals and generates pairs of groups with states, reachable from current pair with this interval
 */
function divide_crossed_intervals($pairofgroups, &$intervals) {
    $fgconditions = array();
    $sgconditions = array();
    $fgtags = array();
    $sgtags = array();
    $fgtagsbegins = array();
    $sgtagsbegins = array();
    $fgstates = array();
    $sgstates = array();
    $usedcharacters = array();
    $prevconditions = array();

    // Adding all transitions to arrays
    foreach ($pairofgroups->first->get_states() as $curstate) {
        $fa = $pairofgroups->first->get_fa();
        foreach ($fa->get_adjacent_transitions($curstate) as $curtransition) {
            $fgconditions[] = $curtransition->pregleaf->get_cachedranges();
            $fgtags[] = count($curtransition->tagsets) ? $curtransition->tagsets[0]->tags : array();
            $fgtagsbegins[] = count($curtransition->tagsets) ? $curtransition->tagsets[0]->tags : array();
            $fgstates[] = $curtransition->to;
        }
    }
    foreach ($pairofgroups->second->get_states() as $curstate) {
        $fa = $pairofgroups->second->get_fa();
        foreach ($fa->get_adjacent_transitions($curstate) as $curtransition) {
            $sgconditions[] = $curtransition->pregleaf->get_cachedranges();
            $sgtags[] = count($curtransition->tagsets) ? $curtransition->tagsets[0]->tags : array();
            $sgtagsbegins[] = count($curtransition->tagsets) ? $curtransition->tagsets[0]->tags : array();
            $sgstates[] = $curtransition->to;
        }
    }

    // For every transition intervals
    while (count($fgconditions) || count($sgconditions)) {
        $curcondchar = 257;
        $charinclude = false;
        $curtags = array();

        // Find next minimal unused transition character from existing
        foreach ($fgconditions as $singleconditions) {
            if (current(current($singleconditions)) < $curcondchar) {
                $curcondchar = current(current($singleconditions));
            }
        }
        foreach ($sgconditions as $singleconditions) {
            if (current(current($singleconditions)) < $curcondchar) {
                $curcondchar = current(current($singleconditions));
            }
        }

        // Check if founded character is included in interval
        foreach ($fgconditions as $singleconditions) {
            if (current(current($singleconditions)) == $curcondchar && key(current($singleconditions)) == 0 ||
                current(current($singleconditions)) != $curcondchar && key(current($singleconditions)) == 1) {
                $charinclude = true;
                break;
            }
        }
        if ($charinclude === false) {
            foreach ($sgconditions as $singleconditions) {
                if (current(current($singleconditions)) == $curcondchar && key(current($singleconditions)) == 0 ||
                    current(current($singleconditions)) != $curcondchar && key(current($singleconditions)) == 1) {
                    $charinclude = true;
                    break;
                }
            }
        }

        // Find all tagsets with this transition
        while (true) {
            // Get maximal tag sequence from transitions, satisfactory to current condition
            $firstinitialization = true;
            $curtags = array();
            for($i = 0; $i < count($fgconditions); $i++) {
                if (current(current($fgconditions[$i])) == $curcondchar && key(current($fgconditions[$i])) == 0 && $charinclude ||
                    current(current($fgconditions[$i])) != $curcondchar && key(current($fgconditions[$i])) == 1 &&
                    (!array_key_exists($curcondchar, $usedcharacters) || current($fgtags[$i]) !== false) && $fgconditions[$i][key($fgconditions[$i])][0] != $curcondchar) {
                    if ($firstinitialization) {
                        $firstinitialization = false;
                        $it = $fgtags[$i];
                        while (current($it) !== false) {
                            $curtags[] = current($it);
                            next($it);
                        }
                    }
                    else {
                        compare_current_transition_tags_array($fgtags[$i], $curtags);
                    }
                }
            }

            for($i = 0; $i < count($sgconditions); $i++) {
                if (current(current($sgconditions[$i])) == $curcondchar && key(current($sgconditions[$i])) == 0 && $charinclude ||
                    current(current($sgconditions[$i])) != $curcondchar && key(current($sgconditions[$i])) == 1 &&
                    (!array_key_exists($curcondchar, $usedcharacters) || current($sgtags[$i]) !== false) && $sgconditions[$i][key($sgconditions[$i])][0] != $curcondchar) {
                    if ($firstinitialization) {
                        $firstinitialization = false;
                        $it = $sgtags[$i];
                        while (current($it) !== false) {
                            $curtags[] = current($it);
                            next($it);
                        }
                    }
                    else {
                        compare_current_transition_tags_array($sgtags[$i], $curtags);
                    }
                }
            }

            // If current tagset is already used with this character - find next character
            if (array_key_exists($curcondchar, $prevconditions) && array_search($curtags, $prevconditions[$curcondchar]) !== false) {
                break;
            }

            // Remember current tagset for current character
            $prevconditions[$curcondchar][] = $curtags;

            // Creating new pair of groups
            $newpairofgroups = new qtype_preg_fa_pair_of_groups();
            $newpairofgroups->first = new qtype_preg_fa_group($pairofgroups->first->get_fa());
            $newpairofgroups->second = new qtype_preg_fa_group($pairofgroups->second->get_fa());
            $newpairofgroups->char = $curcondchar;
            $newpairofgroups->first->set_char($curcondchar);
            $newpairofgroups->second->set_char($curcondchar);
            $newpairofgroups->first->prev_groups = $pairofgroups->first;
            $newpairofgroups->second->prev_groups = $pairofgroups->second;
            $newpairofgroups->tags = $curtags;

            $usedcharacters[$curcondchar] = true;

            // Find all transitions, satisfactory to current one and add destiny states to groups
            for ($i = 0; $i < count($fgconditions); $i++) {
                // Compare character
                if (current(current($fgconditions[$i])) == $curcondchar) {
                    // If it is left (inclusive) border
                    if (key(current($fgconditions[$i])) == 0) {
                        // If current an comparing tagsets are both empty or same
                        if (count($curtags) == 0 && current($fgtags[$i]) === false || count($curtags) != 0
                            && current($fgtags[$i]) !== false && current($fgtags[$i]) == $curtags[0]) {
                            // Add destiny state to group
                            $newpairofgroups->first->add_state($fgstates[$i]);
                            // Push iterator on comparing transition tagset right on current tags count
                            for ($j = 0; $j < count($curtags); $j++) {
                                next($fgtags[$i]);
                            }
                            // If comparing transition tags are off - go to the next transition
                            if (current($fgtags[$i]) === false) {
                                next($fgconditions[$i][key($fgconditions[$i])]);
                                $fgtags[$i] = $fgtagsbegins[$i];
                            }
                        }
                    }
                    // If it is right (exclusive) border
                    else {
                        // Go to next transition and if it doesn't exist - remove arrays
                        if (next($fgconditions[$i]) === false) {
                            array_splice($fgconditions, $i, 1);
                            array_splice($fgtags, $i, 1);
                            array_splice($fgtagsbegins, $i, 1);
                            array_splice($fgstates, $i, 1);
                            $i--;
                        }
                    }
                }
                // If current character is included in charset and current and comparing tagsets are both empty or same
                elseif (key(current($fgconditions[$i])) == 1 && (count($curtags) == 0 && current($fgtags[$i]) === false ||
                        count($curtags) != 0 && compare_tag_sequences($fgtags[$i], $curtags))) {
                    // Add destiny state to group
                    $newpairofgroups->first->add_state($fgstates[$i]);
                }
            }

            for ($i = 0; $i < count($sgconditions); $i++) {
                // Compare character
                if (current(current($sgconditions[$i])) == $curcondchar) {
                    // If it is left (inclusive) border
                    if (key(current($sgconditions[$i])) == 0) {
                        // If current an comparing tagsets are both empty or same
                        if (count($curtags) == 0 && current($sgtags[$i]) === false || count($curtags) != 0
                            && current($sgtags[$i]) !== false && current($sgtags[$i]) == $curtags[0]) {
                            // Add destiny state to group
                            $newpairofgroups->second->add_state($sgstates[$i]);
                            // Push iterator on comparing transition tagset right on current tags count
                            for ($j = 0; $j < count($curtags); $j++) {
                                next($sgtags[$i]);
                            }
                            // If comparing transition tags are off - go to the next transition
                            if (current($sgtags[$i]) === false) {
                                next($sgconditions[$i][key($sgconditions[$i])]);
                                $sgtags[$i] = $sgtagsbegins[$i];
                            }
                        }
                    }
                    // If it is right (exclusive) border
                    else {
                        // Go to next transition and if it doesn't exist - remove arrays
                        if (next($sgconditions[$i]) === false) {
                            array_splice($sgconditions, $i, 1);
                            array_splice($sgtags, $i, 1);
                            array_splice($sgtagsbegins, $i, 1);
                            array_splice($sgstates, $i, 1);
                            $i--;
                        }
                    }
                }
                // If current character is included in charset and current and comparing tagsets are both empty or same
                elseif (key(current($sgconditions[$i])) == 1 && (count($curtags) == 0 && current($sgtags[$i]) === false ||
                        count($curtags) != 0 && compare_tag_sequences($sgtags[$i], $curtags))) {
                    // Add destiny state to group
                    $newpairofgroups->second->add_state($sgstates[$i]);
                }
            }

            // Add new pair of groups to result array if they are not both empty
            if (count($newpairofgroups->first->get_states()) || count($newpairofgroups->second->get_states())) {
                $intervals[] = $newpairofgroups;
            }
        }
    }
}

function divide_intervals($first, $second, $usetags = false) {
    return null;
}